//
//  MinimumTotal.swift
//  LeetCodeSummary
//
//  Created by WangYonghe on 2020/7/14.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  120. 三角形最小路径和

import UIKit

/*
 
 120. 三角形最小路径和
 给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

 相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。

  

 例如，给定三角形：

 [
      [2],
     [3,4],
    [6,5,7],
   [4,1,8,3]
 ]
 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

  

 说明：

 如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。
 
 */

class MinimumTotal: NSObject {
    /*
     将给定的数据置为下图所示
     [2],
     [3,4],
     [6,5,7],
     [4,1,8,3]
     
     设置f(i,j)表示点i,j到底边的最小路径和，则可得出递归求解式：
     f(i,j) = min(f(i+1)(j),f(i+1)(j+1)) + triangle[i][j]
     
     */
    var memoryDic:[[Int]] = []
    let initValue = Int(INT32_MAX)
    
    //递归解法  直接全部计算会超时  加上记忆化可通过，耗时48ms
    func minimumTotal(_ triangle: [[Int]]) -> Int {
       
        self.memoryDic = [[Int]](repeating: [Int](repeating: initValue, count: triangle.count), count: triangle.count)

        return self.dfs(triangle, 0, 0)
    }
    
    func dfs(_ triangle: [[Int]], _ i: Int, _ j: Int) -> Int {

        if  i == triangle.count {
            return 0
        }
        if memoryDic[i][j] != initValue{
            return memoryDic[i][j]
        }else{
            let result = min(self.dfs(triangle, i+1, j), self.dfs(triangle, i+1, j+1))+triangle[i][j]
            memoryDic[i][j] = result
            return result
        }
    }
    
    
    //动态规划解法
    //将递归求解式转为动态转移：dp(i,j) = min(dp(i+1)(j),dp(i+1)(j+1)) + triangle[i][j]
    func minimumTotal2(_ triangle: [[Int]]) -> Int {
        
        let n = triangle.count
        // dp[i][j] 表示从点 (i, j) 到底边的最小路径和。
        var dp = [[Int]](repeating: [Int](repeating: 0, count: n+1), count: n+1)
        //从三角形的最后一行开始遍历
        for i in (0 ... n-1).reversed() {
            for j in (0 ... i){
                dp[i][j] = min(dp[i+1][j],dp[i+1][j+1]) + triangle[i][j]
                print("坐标\(i),\(j)赋值：\(dp[i][j])")
            }
        }
        
        return dp[0][0]
    }
    
}
